from builtins import print as _print
from sys import _getframe


# 自定义print函数 方便输出时候带上行号
def print(*arg, **kw):
	s = f'第{_getframe(1).f_lineno}行：'  # 注此处需加参数 1。
	return _print(s, *arg, **kw)


# ### 1.使用递归实现任意数n的阶乘

# 普通实现
# 5! =5 *4*3*2*1
n = 5
total = 1
for i in range(n, 0, -1):
	total *= i
print(total)  # 120


# 递归实现
def jiecheng(n):
	if n <= 1:
		return 1
	return jiecheng(n - 1) * n


print(jiecheng(2))
# jiecheng(1) => 1
# jiecheng(2) => jiecheng(1) * 2 => 1 * 2
# jiecheng(3) => jiecheng(2) * 3 => 1 * 2 * 3
# jiecheng(4) => jiecheng(3) * 4 => 1 * 2 * 3 * 4
# jiecheng(5) => jiecheng(4) * 5 => 1 * 2 * 3 * 4 * 5
print(jiecheng(5))
"""
代码解析:
去的过程:
n = 5 return jiecheng(n-1) * n => jiecheng(4) * 5
n = 4 return jiecheng(n-1) * n => jiecheng(3) * 4
n = 3 return jiecheng(n-1) * n => jiecheng(2) * 3
n = 2 return jiecheng(n-1) * n => jiecheng(1) * 2
n = 1 return 1

回的过程:
n = 2 return jiecheng(1) * 2 => 1 * 2
n = 3 return jiecheng(2) * 3 => 1 * 2 * 3
n = 4 return jiecheng(3) * 4 => 1 * 2 * 3 * 4
n = 5 return jiecheng(4) * 5 => 1 * 2 * 3 * 4 * 5

到此程序结束:
返回  1 * 2 * 3 * 4 * 5
"""

print("<====================>")
# ### 2. 使用尾递归来实现任意数的阶乘
""" return 在哪调用,在哪返回 """
"""自己调用自己,且返回时非运算表达式,只是函数本身"""
"""
特点:
	尾递归只开辟一个空间,不会无限的开辟,在一个空间里面去计算最后的结果进行返回,比较节省空间,有的解释器支持尾递归的调用特点
	但是cpython解释器目前不支持
写法:
	所有运算的值都在函数的参数中计算完毕,最后返回运算的参数;
"""


def jiecheng(n, endval):
	if n <= 1:
		return endval
	return jiecheng(n - 1, n * endval)


res = jiecheng(5, 1)  # 5*4*3*2*1
print(res)

"""
代码解析:
去的过程
n = 5 ,endval = 1 return jiecheng(n-1 , n * endval) => jiecheng(4,5*1) => 5*1*4*3*2
n = 4 ,endval = 5*1 return jiecheng(n-1 , n * endval) => jiecheng(3,5*1*4) => 5*1*4*3*2 
n = 3 ,endval = 5*1*4 return jiecheng(n-1 , n * endval) => jiecheng(2,5*1*4*3) => 5*1*4*3*2 
n = 2 ,endval = 5*1*4*3 return jiecheng(n-1 , n * endval) => jiecheng(1,5*1*4*3*2) => 5*1*4*3*2 
n = 1 ,endval = 5*1*4*3*2   if n <= 1 成立  return endval
endval = 5*1*4*3*2 
最下层空间的返回值 是 5*4*3*2*1  最上层接收到的返回值也是 5*4*3*2*1
最下层和最上层返回的结果是一致的,所以对于尾递归来说,只需要考虑去的过程,无需考虑回的过程即可完成;
"""


# 优化代码1
def jiecheng(n, endval=1):
	if n <= 1:
		return endval
	return jiecheng(n - 1, n * endval)


res = jiecheng(5, 100)  # 5*4*3*2*1
print(res, "<00000>")


# 优化代码2 [把尾递归需要的参数值隐藏起来,避免篡改.]
def outer(n):
	def jiecheng(n, endval=1):
		if n <= 1:
			return endval
		return jiecheng(n - 1, n * endval)

	return jiecheng(n, 1)  # 120


print(outer(5))


# 优化代码3(扩展)
# 闭包实现
def outer(n):
	endval = 1

	def jiecheng(n):
		nonlocal endval
		if n <= 1:
			return endval
		endval *= n
		return jiecheng(n - 1)

	return jiecheng


func = outer(5)
print(func(5), "<===111==>")

print("<================>")
# ### 3.使用递归来完成斐波那契数列
""" 1 1 2 3 5 8 13 21 34 ... """


def feib(n):
	if n == 1 or n == 2:
		return 1

	# 上一个结果 + 上上个结果
	return feib(n - 1) + feib(n - 2)


print(feib(5))
"""
# 代码解析:
n = 5               feib(5) => 3 + 2 => return 5  
		feib(4)        +         feib(3)
    feib(3)+feib(2)          feib(2)+feib(1) => 1 + 1 => 2
feib(2)+feib(1)+feib(2) => 1 + 1 + 1 => 3    
"""

# 2.青蛙跳台阶  (递归实现)
'''
一只青蛙要跳上n层高的台阶
一次能跳一级,也可以跳两级
请问这只青蛙有多少种跳上这个n层高台阶的方法?

n = 1   1 => 1
n = 2   2 => 1 1 | 2
n = 3   3 => 1 1 1 | 1 2 | 2 1 
n = 4   5 => 1 1 1 1 | 1 2 1 | 2 1 1 | 1 1 2 | 2 2
n = 5   8 => 1 1 1 1 1 | 1 1 1 2 |2 1 1 1 | 1 2 1 1  | 1 1 2 1 | 2 2 1 | 1 2 2 | 2 1 2 
'''


def func(n):
	if n == 1 or n == 2:
		return n
	return func(n - 1) + func(n - 2)


print(func(5))

"""
递归反转字符串 "将14235 反转成53241" (递归实现)"""
# 把后面的字符往前挪动 方法一
strvar = "14235"


# lst.append(5)
# lst.append(3)
# lst.append(2)
# lst.append(4)
# lst.append(1)

# lth = 字符串的总长度  lst 要插入的列表
def func(lth, lst=[]):
	if lth == 0:
		return lst
	res = strvar[lth - 1]
	lst.append(res)
	return func(lth - 1)


lth = len(strvar)
lst = func(lth)
print(lst)  # ['5', '3', '2', '4', '1']
print("".join(lst))


# 简写
def func(lth, lst=[]):
	if lth == 0:
		return "".join(lst)
	res = strvar[lth - 1]
	lst.append(res)
	return func(lth - 1)


print(func(lth))

# 把前面的字符往后挪动 方法二
strvar = "14235"


def func(strvar):
	if len(strvar) == 1:
		return strvar
	return func(strvar[1:]) + strvar[0]


res = func(strvar)
print(res)

"""
递:
return func(4235) + 1
return func(235)  + 4
return func(35)   + 2
return func(5)    + 3
return 5

归:
return func(5)    + 3 => 5 + 3
return func(35)   + 2 => 5 + 3 + 2
return func(235)  + 4 => 5 + 3 + 2 + 4
return func(4235) + 1 => 5 + 3 + 2 + 4 + 1
return 5 + 3 + 2 + 4 + 1
"""

"""
斐波那契数列用尾递归实现
"""
def digui(n):
	lst = []
	"""
		获取斐波那契数列第n位的数值，并返回。
	"""
	def func(n, a=0, b=1):
		if n == 1:
			return b
		return func(n - 1, b, a + b)

	# 将整个斐波那契数列拼接起来并返回。
	for x in range(1, n + 1):
		lst.append(func(x))
	return lst


print(digui(10))
